package Leetcode第二期;

import 多线程.S;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : K k
 * @date : 15:11 2020/9/19
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *  
 *
 * 示例：
 *
 * 输入：n = 3
 * 输出：[
 *        "((()))",
 *        "(()())",
 *        "(())()",
 *        "()(())",
 *        "()()()"
 *      ]
 */
public class 括号生成_22 {

    //思路：回溯
    public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        if (n==0){
            return res;
        }
        dfsSolver("",n,n,res);
        return res;
    }

    //就是棵树
    private void dfsSolver(String ans, int left, int right, List<String> res) {
        if(left==0 && right==0){
            //说明左右括号都为0
            res.add(ans);
            return;
        }
        //剪枝 当left>right的情况要剪掉
        if (left>right){
            return;
        }

        if (left>0){
            dfsSolver(ans+"(",left-1,right,res);
        }
        if (right>0){
            dfsSolver(ans+")",left,right-1,res);
        }
    }
}
